# 中序和后序还原二叉树
from pythonds import BinaryTree


# 先序遍历
def preorderTraversal(root):
    # 保存结果
    result = []

    def traversal(root):
        # 确定终止条件
        if root == None:
            return
        # 前序遍历顺序 中左右
        result.append(root.key)
        traversal(root.getLeftChild())
        traversal(root.getRightChild())

    # 进入traversal()方法
    traversal(root)
    return result


# 中序遍历
def inorderTraversal(root):
    # 保存结果
    result = []

    def traversal(root):
        # 确定终止条件
        if root == None:
            return
        # 前序遍历顺序 左中右
        traversal(root.getLeftChild())
        result.append(root.key)
        traversal(root.getRightChild())

    # 进入traversal()方法
    traversal(root)
    return result


# 后序遍历
def afterorderTraversal(root):
    # 保存结果
    result = []

    def traversal(root):
        # 确定终止条件
        if root == None:
            return
        # 前序遍历顺序 左右中
        traversal(root.getLeftChild())
        traversal(root.getRightChild())
        result.append(root.key)

    # 进入traversal()方法
    traversal(root)
    return result


# 从中序和后序构建二叉树
def buildTree(inorder, postorder):
    # 第一步 递归终止条件 树为空
    if not inorder or not postorder:
        return None

    # 第二步 根节点的值为后序遍历的最后一个元素值
    rootVal = postorder[-1]
    # 创建根节点
    root = BinaryTree(rootVal)

    # 第三步 用根节点的值去中序数组中查找对应元素下标
    midIndex = inorder.index(rootVal)

    # 第四步 找出中序遍历的左子树和右子树
    # 左子树区间为[0,midIndex) , 右子树区间为[midIndex+1,n-1]
    inorderLeft = inorder[:midIndex]
    inorderRight = inorder[midIndex + 1:]

    # 第五步 找出后序遍历的左子树和右子树
    # 后序遍历和中序遍历的左子树和右子树长度相等，所以可以通过中序遍历左右子树的位置
    postorderLeft = postorder[:len(inorderLeft)]
    postorderRight = postorder[len(inorderLeft):len(inorder) - 1]

    # 第六步 递归遍历左右子树
    root.leftChild = buildTree(inorderLeft, postorderLeft)
    root.rightChild = buildTree(inorderRight, postorderRight)

    return root
# 从前序和中序构建二叉树
# def buildTree(preorder,inorder):
#     # 第一步 递归终止条件 树为空
#     if not preorder or not inorder:
#         return None
#     # 第二步 根节点的值为前序遍历的第一个元素值
#     rootVal=preorder[0]
#     # 创建根节点
#     root=BinaryTree(rootVal)
#
#     # 第三步 用根节点的值去中序数组查找对应元素下标
#     midIndex=inorder.index(rootVal)
#
#     # 第四步 找出中序遍历的左子树和右子树
#     # 左子树的区间为[0,midIndex),右子树区间为[midIndex+1,n-1]
#     inorderLeft=inorder[:midIndex]
#     inorderRight=inorder[midIndex+1:]
#
#     # 第五步 找出前序遍历的左子树和右子树
#     # 前序遍历和中序遍历的左子树和右子树长度相等，所以可以通过中序遍历左右子树的位置
#     preorderLeft=preorder[1:len(inorderLeft)+1]
#     preorderRight=preorder[len(inorderLeft)+1:]
#
#     # 第六步递归遍历左右子树
#     root.leftChild=buildTree(preorderLeft,inorderLeft)
#     root.rightChild=buildTree(preorderRight,inorderRight)
#
#     return root

root=buildTree([4,2,1,3,6,5,7],[1,2,3,4,5,6,7])
print("先序遍历:",preorderTraversal(root))
print("中序遍历:",inorderTraversal(root))
print("后序遍历:",afterorderTraversal(root))


